/*  list_reducer.h                  -*-C++-*-
 *
 * Copyright (C) 2011, Intel Corporation
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in
 *     the documentation and/or other materials provided with the
 *     distribution.
 *   * Neither the name of Intel Corporation nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

/*
 * C++ Interface
 *
 * Purpose: Reducer hyperobject for accumulating a list of elements. 
 *
 * Classes: list_append_reducer_ptr<Type, Allocator>
 *          list_prepend_reducer_ptr<Type, Allocator>
 *
 * Description:
 * ============
 * This component provides reducer-type hyperobject representations that allow
 * either prepending or appending values to an STL list.  By replacing the
 * variable with the hyperobject defined in this component, the data race is
 * eliminated.
 *
 * Usage Example:
 * ==============
 * Assume we wish to traverse an array of objects, performing an operation on
 * each object and accumulating the result of the operation into an STL list
 * variable.
 *..
 *  int compute(const X& v);
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern X myArray[ARRAY_SIZE];
 *      // ...
 *
 *      std::list<int> result;
 *      for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          result.push_back(compute(myArray[i]));
 *      }
 *
 *      std::cout << "The result is: ";
 *      for (std::list<int>::iterator i = result.begin(); i != result.end();
 *           ++i)
 *      {
 *          std::cout << *i << " " << std::endl;
 *      }
 *
 *      return 0;
 *  }
 *..
 * Changing the 'for' to a 'cilk_for' will cause the loop to run in
 * parallel, but doing so will create a data race on the 'result'
 * list.  The race is solved by referencing 'result' through an
 * 'list_append_reducer_ptr' hyperpointer.
 *..
 *  int compute(const X& v);
 *
 *  int test()
 *  {
 *      const std::size_t ARRAY_SIZE = 1000000;
 *      extern X myArray[ARRAY_SIZE];
 *      // ...
 *
 *      std::list<int> result;
 *      cilk::list_append_reducer_ptr<int> p_result(&result);
 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
 *      {
 *          p_result->push_back(compute(myArray[i]));
 *      }
 *
 *      std::cout << "The result is: ";
 *      const std::list &r = result.get_value();
 *      for (std::list<int>::iterator i = r.begin(); i != r.end(); ++i)
 *      {
 *          std::cout << *i << " " << std::endl;
 *      }
 *
 *      return 0;
 *  }
 *..
 *
 * Reading and writing the hyperobject: 
 * ====================================
 *
 * 'list_prepend_reducer_ptr' and 'list_append_reducer_ptr' support
 * accumulation of an ordered list of items.  Lists accumulated in
 * Cilk Plus strands will be merged to maintain the order of the
 * lists, i.e., the order will be the same as if the application was
 * run on a single core.
 *
 * In the previous example, 'p_result' is a hyperpointer created from
 * the primary object, 'result'.  Reading or modifying 'result'
 * directly produces deterministic behavior only when performed before
 * the first spawn after creating 'p_result' or when all strands
 * spawned since creating the 'p_result' have been synced.  Using
 * 'result' at other times is likely to create a data race.
 *
 * Normally, in parallel execution, the primary object 'result' is
 * modified only through 'p_result', and only through the appropriate
 * push methods, i.e., 'push_back' for 'list_append_reducer_ptr' or
 * 'push_front' for 'list_prepend_reducer_ptr'.
 * 
 * A strand can also dereference the reducer pointer 'p_result' to
 * access its current view (i.e., '*p_result'), and then read or
 * modify the view by means of the 'get_value_for_current_strand' and
 * 'set_value_for_current_strand' functions, respectively.  As with
 * most reducers, however, the use of these functions may produce
 * nondeterministic results if called in parallel code.
 */

#ifndef LIST_REDUCER_H_INCLUDED
#define LIST_REDUCER_H_INCLUDED

#ifndef __cplusplus
#   error List reducers not yet implemented for C.
#endif

#include "reducer_ptr.h"
#include <list>

namespace cilk
{

/**
 * @brief A wrapper around an STL list where elements are added to the
 * end of the list.
 *
 * An instantiation of list_append_reducer_view is the view type for
 * list_append_reducer_ptr.  In order to prevent user errors, it wraps
 * the list to allow modifications only by appending elements, i.e.,
 * adding them to the end of the list.
 */
template <class _Ty, class _Ax = std::allocator<_Ty> >
class list_append_reducer_view
{
    // Not copyable.
    list_append_reducer_view(const list_append_reducer_view&);
    list_append_reducer_view& operator=(const list_append_reducer_view&);
    
    // The underlying list.
    std::list<_Ty, _Ax> m_value;

  public:
    // Value type. 
    typedef std::list<_Ty, _Ax> value_type;
    
    /// Construct a view with an empty list.
    list_append_reducer_view();
 
    /// Construct a view with the specified initial list.
    list_append_reducer_view(const std::list<_Ty, _Ax> &initial_list);

    /// Return a reference to the current list.
    ///
    /// @warning If this method is called before the parallel calculation is
    /// complete, the value returned by this method will be a partial result.
    std::list<_Ty, _Ax> &get_value_ref();    

    /// Add an element to the end of the list.
    void push_back(const _Ty element);

}; // class list_append_reducer_view


/**
 * @brief Monoid describing the append operation on a list.
 *
 * A monoid is a triple consisting of a type, an associative operation
 * on that type, and an identity for that operation.  For
 * list_append_monoid<_Ty, _Ax>, the view type is std::list<_Ty, _Ax>
 * (i.e., a list of elements of type _Ty), the associative operation
 * is adding to the end of the list, and the identity is an empty
 * list.
 */
template <class _Ty, class _Ax = std::allocator<_Ty> >    
class list_append_monoid :
        public monoid_base2< list_append_reducer_view<_Ty, _Ax> >
{
public:
    /// Append the list 'right' onto the end of the list "left".
    /// The combined list is stored in 'left', and 'right' is emptied.
    static void reduce(list_append_reducer_view<_Ty, _Ax>* left,
		       list_append_reducer_view<_Ty, _Ax>* right);
};

/**
 * @brief A reducer pointer for appending elements to a list.
 *
 * This reducer pointer type is shorthand for
 * reducer_ptr<list_append_monoid<_Ty, _Ax>>.
 */    
template <class _Ty, class _Ax = std::allocator<_Ty> >	
struct list_append_reducer_ptr : reducer_ptr< list_append_monoid<_Ty, _Ax> >
{
    /// Construct a null list_append_reducer_ptr.
    list_append_reducer_ptr();
    
    /// Construct a list_append_reducer_ptr whose primary object is
    /// the list at primary_list_p.
    explicit list_append_reducer_ptr(std::list<_Ty, _Ax>* primary_list_p);

    /// Construct a list_append_reducer_ptr that shares the same
    /// primary object as p.  After construction, this hyperpointer
    /// can be used interchangeably with p.  This constructor is an
    /// implicit conversion constructor from the longhand type name.
    list_append_reducer_ptr(
        const reducer_ptr< list_append_monoid<_Ty, _Ax> >& p);

    /// Make this hyperpointer share the same primary object as p.  After the
    /// assigment, this hyperpointer can be used interchangeably with p.
    list_append_reducer_ptr&
    operator=(const reducer_ptr< list_append_monoid<_Ty, _Ax> >& p);
};


/**
 * @brief A wrapper around an STL list where elements are added to the
 * beginning of a list.
 *
 * An instantiation of list_prepend_reducer_view is the view type for
 * list_prepend_reducer_ptr.  In order to prevent user errors, it
 * wraps the list to allow modifications only by prepending elements,
 * i.e., adding them to the beginning of the list.
 */
template <class _Ty, class _Ax = std::allocator<_Ty> >
class list_prepend_reducer_view
{
    // Not copyable.
    list_prepend_reducer_view(const list_prepend_reducer_view&);
    list_prepend_reducer_view& operator=(const list_prepend_reducer_view&);
    
    // The underlying list.
    std::list<_Ty, _Ax> m_value;

  public:
    // Value type. 
    typedef std::list<_Ty, _Ax> value_type;

    /// Construct a view with an empty list.
    list_prepend_reducer_view();

    /// Construct a view with the specified initial list. 
    list_prepend_reducer_view(const std::list<_Ty, _Ax> &initial_value);

    /// Return a reference to the current list.
    ///
    /// @warning If this method is called before the parallel calculation is
    /// complete, the value returned by this method will be a partial result.
    std::list<_Ty, _Ax> &get_value_ref();

    // Add an element to the beginning of the list.
    void push_front(const _Ty element);

}; // class list_prepend_reducer_view

/**
 * @brief Monoid describing the prepend operation on a list.
 *
 * A monoid is a triple consisting of a type, an associative operation
 * on that type, and an identity for that operation.  For
 * list_append_monoid<_Ty, _Ax>, the view type is std::list<_Ty, _Ax>
 * (i.e., a list of elements of type _Ty), the associative operation
 * is adding to the beginning of the list, and the identity is an
 * empty list.
 */
template <class _Ty, class _Ax = std::allocator<_Ty> >    
class list_prepend_monoid :
    public monoid_base2< list_prepend_reducer_view<_Ty, _Ax> >
{
public:

    /// Prepend the list 'right' onto the beginning of the list
    /// 'left'.  The combined list is stored in 'left' and 'right' is
    /// emptied.
    static void reduce(list_prepend_reducer_view<_Ty, _Ax>* left,
		       list_prepend_reducer_view<_Ty, _Ax>* right);
};

/**
 * @brief A reducer pointer for prepending elements to a list.
 *
 * This reducer pointer type is shorthand for
 * reducer_ptr<list_prepend_monoid<_Ty, _Ax>>.
 */    
template <class _Ty, class _Ax = std::allocator<_Ty> >	
struct list_prepend_reducer_ptr : reducer_ptr< list_prepend_monoid<_Ty, _Ax> >
{
    /// Construct a null list_prepend_reducer_ptr.
    list_prepend_reducer_ptr();
    
    /// Construct a list_prepend_reducer_ptr whose primary object is
    /// the list at primary_list_p.
    explicit list_prepend_reducer_ptr(std::list<_Ty, _Ax>* primary_list_p);

    /// Construct a list_prepend_reducer_ptr that shares the same
    /// primary object as p.  After construction, this hyperpointer
    /// can be used interchangeably with p.  This constructor is an
    /// implicit conversion constructor from the longhand type name.
    list_prepend_reducer_ptr(
        const reducer_ptr< list_prepend_monoid<_Ty, _Ax> >& p);

    /// Make this hyperpointer share the same primary object as p.  After the
    /// assigment, this hyperpointer can be used interchangeably with p.
    list_prepend_reducer_ptr&
    operator=(const reducer_ptr< list_prepend_monoid<_Ty, _Ax> >& p);
};



/////////////////////////////////////////////////////////////////////////////
// Implementation of inline and template functions
/////////////////////////////////////////////////////////////////////////////

// -------------------------------------------------
// template class list_append_reducer_view<_Ty, _Ax>
// -------------------------------------------------

/**
 * Construct a view with an empty list.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 */
template <class _Ty, class _Ax>
inline
list_append_reducer_view<_Ty, _Ax>::list_append_reducer_view() 
    : m_value()
{
}

/**
 * Construct a reducer with the specified initial list.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param initial_value - [in] Initial list
 */
template <class _Ty, class _Ax>
inline
list_append_reducer_view<_Ty, _Ax>::list_append_reducer_view(
    const std::list<_Ty, _Ax> &initial_value) 
    : m_value(std::list<_Ty, _Ax>(initial_value))
{
}

/**
 * Return a reference to the current list.
 * Allows mutable access to list.
 *
 * @warning If this method is called before the parallel calculation is
 * complete, the list returned by this method will be a partial result.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @returns A reference to the list that is the current contents of this view.
 */
template <class _Ty, class _Ax>
inline
std::list<_Ty, _Ax>&
list_append_reducer_view<_Ty, _Ax>::get_value_ref() 
{
    return m_value;
}

/**
 * Add an element to the end of the list.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param element - The element to be added to the end of the list
 */
template <class _Ty, class _Ax>
inline
void
list_append_reducer_view<_Ty, _Ax>::push_back(const _Ty element) 
{
    m_value.push_back(element);
}


// -------------------------------------------
// template class list_append_monoid<_Ty, _Ax>
// -------------------------------------------

/**
 * Append the list 'right' onto the end of the list "left".
 * The combined list is stored in 'left', and 'right' is emptied.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param left reducer_list to be reduced into
 * @param right reducer_list to be reduced from
 */
template <class _Ty, class _Ax >    
void
list_append_monoid<_Ty, _Ax>::reduce(list_append_reducer_view<_Ty, _Ax>* left,
				     list_append_reducer_view<_Ty, _Ax>* right)
{
    std::list<_Ty, _Ax>& left_ref = left->get_value_ref();
    std::list<_Ty, _Ax>& right_ref = right->get_value_ref();
    left_ref.splice(left_ref.end(), right_ref);
}

// ------------------------------------------------
// template class list_append_reducer_ptr<_Ty, _Ax>
// ------------------------------------------------

template <class _Ty, class _Ax>	
inline
list_append_reducer_ptr<_Ty, _Ax>::list_append_reducer_ptr() 
    : reducer_ptr< list_append_monoid<_Ty, _Ax> >()
{
}

template <class _Ty, class _Ax>	
inline
list_append_reducer_ptr<_Ty, _Ax>::list_append_reducer_ptr(
    std::list<_Ty, _Ax>* primary_list_p)
    : reducer_ptr< list_append_monoid<_Ty, _Ax> >(primary_list_p)
{
}

template <class _Ty, class _Ax>	
inline
list_append_reducer_ptr<_Ty, _Ax>::list_append_reducer_ptr(
    const reducer_ptr< list_append_monoid<_Ty, _Ax> >& p)
    : reducer_ptr< list_append_monoid<_Ty, _Ax> >(p)
{
}

template <class _Ty, class _Ax>	
inline
list_append_reducer_ptr<_Ty, _Ax>&
list_append_reducer_ptr<_Ty, _Ax>::operator=(
    const reducer_ptr< list_append_monoid<_Ty, _Ax> >& p)
{
    reducer_ptr< list_append_monoid<_Ty, _Ax> >::operator=(p);
    return *this;
}


// --------------------------------------------------
// template class list_prepend_reducer_view<_Ty, _Ax>
// --------------------------------------------------

/**
 * Construct a view with an empty list.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 */
template <class _Ty, class _Ax>
inline
list_prepend_reducer_view<_Ty, _Ax>::list_prepend_reducer_view() 
    : m_value()
{
}

/**
 * Construct a view with the specified initial list. 
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param initial_value - [in] Initial list
 */
template <class _Ty, class _Ax>
inline
list_prepend_reducer_view<_Ty, _Ax>::list_prepend_reducer_view(
    const std::list<_Ty, _Ax> &initial_value) 
    : m_value(std::list<_Ty, _Ax>(initial_value))
{
}

/**
 * Return a reference to the current list.
 * Allows mutable access to list.
 *
 * @warning If this method is called before the parallel calculation is
 * complete, the list returned by this method will be a partial result.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @returns A reference to the list that is the current contents of this view.
 */
template <class _Ty, class _Ax>
inline
std::list<_Ty, _Ax>&
list_prepend_reducer_view<_Ty, _Ax>::get_value_ref() 
{
    return m_value;
}

/**
 * Add an element to the beginning of the list.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param element - The element to be added to the end of the list
 */
template <class _Ty, class _Ax>
inline
void
list_prepend_reducer_view<_Ty, _Ax>::push_front(const _Ty element) 
{
    m_value.push_front(element);
}


// --------------------------------------------
// template class list_prepend_monoid<_Ty, _Ax>
// --------------------------------------------

/**
 * Prepend the list 'right' onto the beginning of the list 'left'.
 * The combined list is stored in 'left' and 'right' is emptied.
 *
 * @tparam _Ty - Type of the list elements
 * @tparam _Ax - Allocator object used to define the storage allocation
 * model.  If not specified, the allocator class template for _Ty is used.
 * @param left reducer_list to be reduced into
 * @param right reducer_list to be reduced from
 */
template <class _Ty, class _Ax>    
void
list_prepend_monoid<_Ty, _Ax>::reduce(
    list_prepend_reducer_view<_Ty, _Ax>* left,
    list_prepend_reducer_view<_Ty, _Ax>* right)
{
    std::list<_Ty, _Ax>& left_ref = left->get_value_ref();
    std::list<_Ty, _Ax>& right_ref = right->get_value_ref();
    left_ref.splice(left_ref.begin(), right_ref);
}

// -------------------------------------------------
// template class list_prepend_reducer_ptr<_Ty, _Ax>
// -------------------------------------------------

template <class _Ty, class _Ax>	
inline
list_prepend_reducer_ptr<_Ty, _Ax>::list_prepend_reducer_ptr() 
    : reducer_ptr< list_prepend_monoid<_Ty, _Ax> >()
{
}

template <class _Ty, class _Ax>	
inline
list_prepend_reducer_ptr<_Ty, _Ax>::list_prepend_reducer_ptr(
    std::list<_Ty, _Ax>* primary_list_p)
    : reducer_ptr< list_prepend_monoid<_Ty, _Ax> >(primary_list_p)
{
}

template <class _Ty, class _Ax>	
inline
list_prepend_reducer_ptr<_Ty, _Ax>::list_prepend_reducer_ptr(
    const reducer_ptr< list_prepend_monoid<_Ty, _Ax> >& p)
    : reducer_ptr< list_prepend_monoid<_Ty, _Ax> >(p)
{
}

template <class _Ty, class _Ax>	
inline
list_prepend_reducer_ptr<_Ty, _Ax>&
list_prepend_reducer_ptr<_Ty, _Ax>::operator=(
    const reducer_ptr< list_prepend_monoid<_Ty, _Ax> >& p)
{
    reducer_ptr< list_prepend_monoid<_Ty, _Ax> >::operator=(p);
    return *this;
}

}      // namespace cilk

#endif // LIST_REDUCER_H_INCLUDED
